#ifndef SPARSE_MATRIX_CC
#define SPARSE_MATRIX_CC

#include "SparseMatrix.h"

template <typename T>
SparseMatrix<T> :: SparseMatrix(UINT nrows, UINT ncols, ULONG nterms)
{
    if (nrows == 0 || ncols == 0 || nrows * ncols < nterms) {
        throw MatrixException(INVALID_DIMENSIONS);
    }
    setRows(nrows);
    setCols(ncols);
    setTerms(nterms);
    _entries = new (std :: nothrow) MatrixEntry<T> *[nterms];
    if (_entries == NULL) {
        throw MatrixException(NO_MEMORY);
    }
    for (ULONG i = 0; i < nterms; i++) {
        _entries[i] = NULL;
    }
}

template <typename T>
SparseMatrix<T> :: ~SparseMatrix()
{
    UINT nterms = getTerms();

    if (_entries != NULL) {
        while (--nterms != UMAX) {
            if (_entries[nterms] != NULL) {
                delete _entries[nterms];
                _entries[nterms] = NULL;
            }
        }
        delete[] _entries;
        setTerms((ULONG)0);
        setRows((UINT)0);
        setCols((UINT)0);
        _entries = NULL;
    }
}

template <typename T>
void SparseMatrix<T> :: setRows(UINT nrows)
{
    _nrows = nrows;
}

template <typename T>
void SparseMatrix<T> :: setCols(UINT ncols)
{
    _ncols = ncols;
}

template <typename T>
void SparseMatrix<T> :: setTerms(ULONG nterms)
{
    _nterms = nterms;
}

template <typename T>
UINT SparseMatrix<T> ::  getRows()
{
    return _nrows;
}
template <typename T>
UINT SparseMatrix<T> :: getCols()
{
    return _ncols;
}

template <typename T>
ULONG SparseMatrix<T> :: getTerms()
{
    return _nterms;
}

template <typename T>
BOOL SparseMatrix<T> :: resize(ULONG new_size)
{
    MatrixEntry<T> **newspace;
    ULONG i;
    ULONG nterms;

    nterms = getTerms();
    if (nterms > new_size) {
        cerr << SIZE_INVALID << endl;
        return FALSE;
    }
    newspace = new (std :: nothrow) MatrixEntry<T>*[new_size];
    if (newspace == NULL) {
        cerr << NO_MEMORY << endl;
        return FALSE;
    }

    for (i = 0; i < nterms; i++) {
        newspace[i] = _entries[i];
    }
    for (; i < new_size; i++) {
        newspace[i] = NULL;
    }
    delete[] _entries;
    _entries = newspace;
    return TRUE;
}

template <typename T>
BOOL SparseMatrix<T> :: append(MatrixEntry<T> *add_me,
                            ULONG nterms,
                            BOOL copy)
{
    ULONG si; /** start index*/
    ULONG i;
    MatrixEntry<T> *e;
    
    if (nterms == 0) {
        return TRUE;
    } else if (add_me == NULL) {
        return FALSE;
    }
    /* resize the matrix to hold nterms more elements*/
    si = getTerms();
    i = 0;
    if (resize(si + nterms) == FALSE) {
        return FALSE;
    }
    /* append the elements */
    while (nterms-- != 0) {
        if (copy == FALSE) {
            e = add_me + i;
        } else if (copy == TRUE) {
            e = new (std :: nothrow) MatrixEntry<T>(add_me + i);
            if (e == NULL) {
                cerr << "NO MEMORY" << endl;
                setTerms(si - 1);
                return FALSE;
            }
        } else {
            cerr << "INVALID COPY VALUE" << endl;
            setTerms(si - 1);
            return FALSE;
        }
        _entries[si++] = e;
    }
    setTerms(si);
    return TRUE;
}

template <typename T>
BOOL SparseMatrix<T> :: assign(MatrixEntry<T> *add_me, ULONG si,
                            ULONG nterms, BOOL copy)
{
    MatrixEntry<T> *e;

    if (nterms == 0) {
        return TRUE;
    } else if (add_me == NULL) {
        return FALSE;
    }
    /* add the elements */
    while (nterms-- != 0) {
        if (copy == FALSE) {
            e = add_me;
        } else if (copy == TRUE) {
            e = new (std :: nothrow) MatrixEntry<T>(add_me);
            if (e == NULL) {
                cerr << "NO MEMORY" << endl;
                setTerms(si - 1);
                return FALSE;
            }
        } else {
            cerr << "INVALID COPY VALUE" << endl;
            setTerms(si - 1);
            return FALSE;
        }
        _entries[si++] = e;
        add_me++;
    }
    return TRUE;
}

template <typename T>
void SparseMatrix<T> :: print()
{
    ULONG terms;

    if (_entries == NULL) {
        return;
    }
    terms = getTerms();
    for (ULONG i = 0; i < terms; i++) {
        _entries[i]->print();
    }
}

template <typename T>
SparseMatrix<T> * SparseMatrix<T> :: init(const char *filename)
{
    ifstream f;
    ULONG i;
    UINT col;
    ULONG nrows;
    ULONG ncols;
    ULONG nterms;
    UINT row;
    UINT prev_row;
    UINT prev_col;
    T value;
    SparseMatrix<T> *dst;
    MatrixEntry<T> *entry;

    dst = NULL;
    if (filename == NULL) {
        cerr << "FAILED ERROR CHECK" << endl;
        goto done;
    }
    f.open(filename);
    //read in the dimensions.
    if (f.good() == FALSE || f.eof()) {
        goto done;
    }
    f >> nrows;
    f >> ncols;
    f >> nterms;
    try {
        dst = new (std :: nothrow) SparseMatrix<T>(nrows, ncols, nterms);
    } catch (exception &e) {
        cerr << e.what();
    }
    if (dst == NULL) {
        f.close();
        goto done;
    }
    //read the rest of the data
    prev_col = prev_row = i = 0;
    while (nterms-- != 0) {
        f >> row;
        f >> col;
        f >> value;
        if (f.good() == FALSE) {
            delete dst;
            dst = NULL;
            goto done;
        }
        if (row >= nrows ||
            col >= ncols ||
            prev_col > col ||
            prev_row > row) {
            cerr << "invalid row, col : " << row << ", " << col << endl;
            delete dst;
            dst = NULL;
            goto done;
        }
        prev_col = col;
        prev_row = row;
        entry = new (std :: nothrow) MatrixEntry<T>(row, col, value);
        if (entry == NULL) {
            cerr << "NO SPACE LEFT" << endl;
            delete dst;
            dst = NULL;
            break;
        }
        dst->_entries[i++] = entry;
    }
done:
    if (f.is_open()) {
        f.close();
    }
    return dst;
}

template <typename T>
BOOL SparseMatrix<T> :: transpose(SparseMatrix<T> *dst)
{
    UINT ncols;
    ULONG nterms;
    UINT *count;
    ULONG *start_indices;
    UINT i;
    UINT cur_col;
    MatrixEntry<T> *entry;
    
    ncols = getCols();
    nterms = getTerms();

    if (dst == NULL ||
        dst->_entries == NULL ||
        _entries == NULL ||
        ncols != dst->getRows() ||
        getRows() != dst->getCols() ||
        nterms != dst->getTerms() ) {
        cerr << __FILE__ << __LINE__ << "Error Checks fail" << endl;
        goto done;
    }

    count = new (std :: nothrow) UINT[ncols];
    if (count == NULL) {
        cerr << "COUNT array is NULL" << endl;
        goto done;
    }
    for (UINT i = 0; i < ncols; i++) {
        count[i] = 0;
    }
    start_indices = new (std :: nothrow) ULONG[ncols];
    if (start_indices == NULL) {
        cerr << "start_indices array is NULL" << endl;
        goto done;
    }
    for (i = 0; i < nterms; i++) {
        count[_entries[i]->getCol()]++;
    }
    start_indices[0] = 0;
    for (i = 1; i < ncols; i++) {
        start_indices[i] = start_indices[i - 1] + count[i - 1];
    }
    
    delete[] count;
    // this is the main loop for the fast transpose
    for (ULONG i = 0; i < nterms; i++) {
        cur_col = _entries[i]->getCol();
        entry = new (std :: nothrow) MatrixEntry<T>(_entries[i], TRUE);
        if (entry == NULL) {
            cerr << "NO SPACE" << endl;
            delete[] start_indices;
            goto done;
        }
        dst->_entries[start_indices[cur_col]++] = entry;
    }
    delete[] start_indices;
    return TRUE;
done:
    return FALSE;
}

template <typename T>
SparseMatrix<T> *SparseMatrix<T> :: operator+(SparseMatrix<T> &add_me)
{
    UINT nrows;
    UINT ncols;
    ULONG aterms;
    ULONG bterms;
    ULONG ai;
    ULONG bi;
    ULONG si;
    SparseMatrix<T> *sum;
    MatrixEntry<T> *ca;
    MatrixEntry<T> *cb;
    MatrixEntry<T> *e;

    if ((nrows = getRows()) != add_me.getRows() ||
         (ncols = getCols()) != add_me.getCols()) {
        cerr << "DIMENSIONS do not match" << endl;
        return NULL;
    }
    aterms = getTerms();
    bterms = add_me.getTerms();
    // we don't know the number of terms yet.
    sum = new (std :: nothrow) SparseMatrix<T>(nrows, ncols, 0);
    if (sum == NULL) {
        cerr << "NO MEMORY LEFT" << endl;
        return NULL;
    }
    ai = bi = si = 0;
    while (aterms >= ai && bterms >= bi) {
        if (aterms == ai) {
            if (sum->append(add_me._entries[bi], bterms - bi, TRUE) == TRUE) {
                break;
            }
            goto cleanup;
        } else if (bterms == bi) {
            if (sum->append(_entries[ai], aterms - ai, TRUE) == TRUE) {
                break;
            }
            goto cleanup;
        }
        ca = _entries[ai];
        cb = add_me._entries[bi];

        if ((*ca == *cb) == TRUE) {
            e = new (std :: nothrow) MatrixEntry<T>(ca->getRow(),
                                                  ca->getCol(),
                                                  ca->getVal() + cb->getVal());
            if (e == NULL) {
                cerr << "PROBLEM OCCURRECD IN ADDITION" << endl;
                goto cleanup;
            }
            if (sum->append(e, 1) != TRUE) {
                delete e;
                goto cleanup;
            }
            ai++;
            bi++;

        } else if ((*ca < *cb) == TRUE) {
            if (sum->append(_entries[ai], 1, TRUE) != TRUE) {
                goto cleanup;
            }
            ai++;
        } else {
            if (sum->append(add_me._entries[bi], 1, true) == FALSE) {
                goto cleanup;
            }
            bi++;
        }

    }
    return sum;
cleanup:
    if (sum != NULL) {
        delete sum;
    }
    return NULL;

}

template <typename T>
ULONG SparseMatrix<T> :: count_add_entries(SparseMatrix<T> &a,
                                           SparseMatrix<T> &b)
{
    ULONG aterms;
    ULONG bterms;
    ULONG count;
    ULONG ai;
    ULONG bi;

    aterms = a.getTerms();
    bterms = b.getTerms();
    ai = bi = count = 0;
    while (ai <= aterms && bi <= bterms) {
        if (ai == aterms) {
            count += (bterms - bi);
            break;
        } else if (bi == bterms) {
            count += (aterms - ai);
            break;
        } else if ((*(a._entries[ai]) == *(b._entries[bi])) == TRUE) {
            ai++;
            bi++;
        } else if ((*(a._entries[ai]) < *(b._entries[bi])) == TRUE) {
            ai++;
        } else {
            bi++;
        }
        count++;
    }
    return count;
}

template <typename T>
SparseMatrix<T> *SparseMatrix<T> :: faster_add(SparseMatrix<T> &add_me)
{
    UINT nrows;
    UINT ncols;
    ULONG aterms;
    ULONG bterms;
    ULONG ai;
    ULONG bi;
    ULONG si;
    ULONG count;
    SparseMatrix<T> *sum;
    MatrixEntry<T> *ca;
    MatrixEntry<T> *cb;
    MatrixEntry<T> *e;

    if ((nrows = getRows()) != add_me.getRows() ||
         (ncols = getCols()) != add_me.getCols()) {
        cerr << "DIMENSIONS do not match" << endl;
        return NULL;
    }
    aterms = getTerms();
    bterms = add_me.getTerms();
    count = count_add_entries(*this, add_me);
    sum = new (std :: nothrow) SparseMatrix<T>(nrows, ncols, count);
    if (sum == NULL) {
        cerr << "NO MEMORY LEFT" << endl;
        return NULL;
    }
    
    ai = bi = si = 0;
    while (aterms >= ai && bterms >= bi) {
        if (aterms == ai) {
            if (sum->assign(add_me._entries[bi], si, bterms - bi, TRUE)
                        == TRUE) {
                break;
            }
            goto cleanup;
        } else if (bterms == bi) {
            if (sum->assign(_entries[ai], si, aterms - ai, TRUE) == TRUE) {
                break;
            }
            goto cleanup;
        }
        ca = _entries[ai];
        cb = add_me._entries[bi];

        if (*ca == *cb) {
            e = new (std :: nothrow) MatrixEntry<T>(ca->getRow(),
                                                  ca->getCol(),
                                                  ca->getVal() + cb->getVal());
            if (e == NULL) {
                cerr << "PROBLEM OCCURRECD IN ADDITION" << endl;
                goto cleanup;
            }
            if (sum->assign(e, si, 1) != TRUE) {
                delete e;
                goto cleanup;
            }
            ai++;
            bi++;

        } else if (*ca < *cb) {
            if (sum->assign(_entries[ai], si, 1, TRUE) != TRUE) {
                goto cleanup;
            }
            ai++;
        } else {
            if (sum->assign(add_me._entries[bi], si, 1, TRUE) == FALSE) {
                goto cleanup;
            }
            bi++;
        }
        si++;
    }
    return sum;
cleanup:
    if (sum != NULL) {
        delete sum;
    }
    return NULL;

}



template <typename T>
SparseMatrix<T> * SparseMatrix<T> :: operator*(SparseMatrix<T> &b)
{
    UINT a_ncols; /* # of colums in this matrix*/
    UINT b_nrows; /* # of rows in b matrix*/
    ULONG a_nterms; /* # of terms in this matrix*/
    ULONG b_nterms; /* # of colums in b matrix*/
    ULONG ai; /* current index within matrix a*/
    ULONG bt_i; /* current index withing matrix b*/
    UINT ar;
    UINT bt_r;
    UINT car;/* current row in a being processed in Matrix a*/
    UINT cbr; /* current column being processed in Matrix b*/
    UINT a_row_start; /* start position of current row*/
    UINT bt_row_start;
    BOOL status;
    SparseMatrix<T> *bt; /*transpose of b matrix*/
    SparseMatrix<T> *r; /* resultant matrix of Matrix a * Matrix b */
    MatrixEntry<T> **aentries;
    MatrixEntry<T> **btentries;
    list<MatrixEntry<T> *> *tlist; /* holds the individual colums as list */
    MatrixEntry<T> *temp;
    T cur_sum;

    bt = NULL;
    r = NULL;
    tlist = NULL;
    a_ncols = getCols();
    b_nrows = b.getRows();
    if (a_ncols != b_nrows) {
        throw MatrixException(CANNOT_MULTIPLY);
    }
    
    //check for empty matrices.
    a_nterms = getTerms();
    b_nterms = b.getTerms();
    if (a_nterms == 0 || b_nterms == 0) {
        r = new (std :: nothrow) SparseMatrix<T>(getRows(),
                                                 b.getCols(),
                                                 0);
        if (r == NULL) {
            throw MatrixException(NO_MEMORY);
        }
        return r;
    }

    bt = new (std :: nothrow) SparseMatrix<T>(a_ncols,
                                               b_nrows, b.getTerms());
    if (bt == NULL) {
        throw MatrixException(NO_MEMORY);
    }
    try {
        status = b.transpose(bt);
        if (status == FALSE) {
            cerr << "problem with transpose" << endl;
            goto error;
        }
    } catch (exception &e) {
        cerr << e.what() << endl;
        goto error;
    }
    tlist = new (std :: nothrow) list<MatrixEntry<T> *>();
    if (tlist == NULL) {
        throw MatrixException(NO_MEMORY);
        goto error;
    }
    
    ai = 0;
    bt_i = 0;
    cbr = 0;
    car = 0;
    a_row_start = 0;
    bt_row_start = 0;
    a_nterms = getTerms();
    b_nterms = b.getTerms();
    aentries = _entries;
    btentries = bt->_entries;
    cur_sum = T();

    while (ai <= a_nterms) {
        ai = a_row_start;
        bt_i = 0;
        car = _entries[ai]->getRow();
        cbr = bt->_entries[bt_i]->getRow();
        
        while (bt_i < b_nterms) {

            if (ai == a_nterms) {
                ai = a_row_start;
            }

            ar = _entries[ai]->getRow();
            bt_r = bt->_entries[bt_i]->getRow();

            if (ar != car || bt_r != cbr) {
                if (cur_sum != T()) {
                    temp = new (std :: nothrow) MatrixEntry<T>(car,
                                                               cbr,
                                                               cur_sum);
                    if (temp == NULL) {
                        goto error;
                    }
                    tlist->push_back(temp);
                    cur_sum = T();
                }
                ai = a_row_start;
                cbr = bt_r;
            } else {
                cur_sum += _entries[ai]->getVal() * bt->_entries[bt_i]->getVal();
                ai++;
                bt_i++;
            }
        } // end of inner while loop.
        
        /* Don't leave out the last term*/
        if (cur_sum != T()) {
            temp = new (std :: nothrow) MatrixEntry<T>(car,
                                                    cbr,
                                                    cur_sum);
            cur_sum = T();
            if (temp == NULL) {
                goto error;
            }
            tlist->push_back(temp);
        }
        /*move the start index to the next row*/
        while (ai < a_nterms && aentries[ai]->getRow() == car) {
            ai++;
        }
        if (ai == a_nterms) {
            break;
        }
        a_row_start = ai;
    }
    //move the result to r;
    r = new (std :: nothrow) SparseMatrix<T>(getRows(),
                                             b.getCols(),
                                             tlist->size());
    if (r == NULL) {
        throw MatrixException(NO_MEMORY);
    }
    ai = 0;
    for (typename list<MatrixEntry<T> *>::iterator my_iter = tlist->begin();
            my_iter != tlist->end(); my_iter++) {
        r->_entries[ai++] = *my_iter;
        *my_iter = NULL;
    }
    delete bt;
    delete tlist;
    return r;
    
error:
    if (bt != NULL) {
        delete bt;
    }
    if (r != NULL) {
        delete r;
    }
    if (tlist != NULL) {
        delete tlist;
    }
    return NULL;

}


#endif
